package com.leetcode;

import com.leetcode.common.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 234. 回文链表
 * 将值复制到数组中后用双指针法(题目要求是用O(1)时间复杂度)
 *
 * @author fy
 * @date 2022/4/11 21:44
 */
public class Solution234_2 {

    public boolean isPalindrome(ListNode head) {
        // 如果为null或者只有一个节点, 肯是回文链表
        if (head == null || head.next == null) {
            return true;
        }
        // 将值复制到list中后用双指针法
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        // 使用双指针判断是否回文
        int p = 0;
        int q = list.size() - 1;
        while (p < q) {
            if (!list.get(p).equals(list.get(q))) {
                return false;
            }
            p++;
            q--;
        }
        return true;
    }

}
